//给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足： 
//
// 
// 0 <= i, j, k, l < n 
// nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
//输出：2
//解释：
//两个元组如下：
//1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1)
// + 2 = 0
//2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1)
// + 0 = 0
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// n == nums1.length 
// n == nums2.length 
// n == nums3.length 
// n == nums4.length 
// 1 <= n <= 200 
// -2²⁸ <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2²⁸ 
// 
//
// Related Topics 数组 哈希表 👍 972 👎 0


package leetcode.editor.cn;

import java.util.HashMap;

/**
 * 四数相加 II
 * @author CodeTheory
 * @date 2024-02-26 11:06:43
 */
public class P454_FourSumIi{
	 public static void main(String[] args) {
	 	 Solution solution = new P454_FourSumIi().new Solution();
		 System.out.println(solution.fourSumCount(new int[]{1, 2}, new int[]{-2, -1}, new int[]{-1, 2}, new int[]{0, 2}));
		 System.out.println(solution.fourSumCount(new int[]{0}, new int[]{0}, new int[]{0}, new int[]{0}));
		 int[] nums1 = {-268434543,-268434778,-268435208,-268434948,-268435390,-268435258,-268435289,-268434617,-268435342,-268434922,-268435335,-268434715,-268435400,-268435185,-268434954,-268435137,-268435347,-268435033,-268434503,-268435311,-268435232,-268434779,-268435053,-268434707,-268435036,-268434992,-268434657,-268434765,-268434865,-268435101,-268434896,-268435278,-268434732,-268434645,-268435157,-268435159,-268434992,-268434926,-268435392,-268435189,-268434917,-268434970,-268435118,-268434628,-268434910,-268434900,-268434498,-268435095,-268434590,-268435056,-268434510,-268435262,-268434917,-268434656,-268435001,-268435305,-268434595,-268434997,-268435373,-268434600,-268435166,-268434863,-268434960,-268435299,-268435292,-268434737,-268434749,-268434475,-268435015,-268434942,-268435006,-268434836,-268435068,-268435432,-268434460,-268435135,-268434877,-268435047,-268434545,-268435171,-268434784,-268435301,-268434939,-268434996,-268435000,-268434837,-268435377,-268434755,-268434955,-268435412,-268434724,-268434631,-268435113,-268435296,-268434505,-268435292,-268435071,-268435304,-268435058,-268434562};
		 int[] nums2 = {-268434750,-268435259,-268434823,-268435095,-268434566,-268435280,-268434753,-268435210,-268434616,-268435294,-268435414,-268434745,-268435196,-268435225,-268434535,-268434746,-268435416,-268435298,-268434836,-268434975,-268434712,-268434720,-268435142,-268435091,-268434568,-268435044,-268435433,-268434915,-268434792,-268434947,-268434969,-268435133,-268434973,-268434997,-268435348,-268435203,-268434692,-268435021,-268434689,-268434677,-268435291,-268434833,-268434577,-268435130,-268435387,-268434650,-268434797,-268435376,-268435244,-268434503,-268435433,-268434729,-268434825,-268434727,-268434738,-268435256,-268435340,-268434750,-268435173,-268435310,-268435078,-268435453,-268435037,-268434638,-268434897,-268434983,-268434865,-268434510,-268435063,-268434512,-268434995,-268435048,-268434788,-268435430,-268434596,-268434515,-268434843,-268435235,-268435041,-268435194,-268435141,-268435150,-268434643,-268435013,-268434590,-268435261,-268435256,-268434799,-268434697,-268434609,-268434861,-268434687,-268434732,-268435031,-268434542,-268434946,-268434542,-268435085,-268435337,-268435233};
		 int[] nums3 = {268435123,268434786,268434802,268435142,268434477,268434984,268434962,268434956,268435125,268434457,268435295,268435014,268434895,268434895,268435285,268435141,268434822,268434661,268435106,268435446,268435275,268434652,268434600,268435268,268434858,268434701,268435439,268434582,268435099,268434701,268435444,268434576,268435179,268434786,268435213,268435064,268434829,268434559,268434611,268435214,268434857,268435134,268434992,268435418,268434915,268435342,268434626,268434987,268434712,268435005,268434666,268435297,268434665,268435082,268434524,268434798,268434708,268435011,268434978,268435299,268435035,268435026,268435324,268434603,268435230,268435247,268435119,268434660,268435053,268434613,268434766,268434718,268434794,268434714,268434860,268434949,268434597,268434489,268435099,268435148,268434560,268435150,268435360,268434937,268435019,268434867,268435084,268435442,268434483,268435396,268435292,268435325,268434912,268435391,268434483,268435441,268434640,268435034,268435395,268435059};
		 int[] nums4 = {268435003,268435419,268434638,268434623,268434978,268434780,268435037,268434800,268434864,268435367,268435082,268434465,268435075,268435043,268434858,268434912,268435313,268434636,268434547,268434462,268435015,268434739,268434807,268434485,268434644,268434757,268434758,268435350,268434942,268434586,268434742,268435308,268434612,268435133,268434863,268434563,268434479,268435143,268434568,268434824,268435332,268435406,268434534,268435219,268435423,268435247,268435416,268435032,268435379,268434559,268435245,268435169,268434774,268435153,268435097,268435317,268434875,268435446,268435296,268434991,268434914,268434846,268434600,268434580,268435176,268435324,268434723,268435078,268435117,268435372,268435262,268434924,268435299,268435382,268434541,268435423,268434870,268435318,268435232,268434721,268434469,268435308,268434504,268434819,268434604,268434829,268435356,268435307,268434938,268435171,268435094,268435327,268434603,268434629,268434902,268435272,268434569,268434973,268434690,268435383};
		 // 67911
		 System.out.println(solution.fourSumCount(nums1, nums2, nums3, nums4));
	 }
	 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
		int res = 0;
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i : nums1) {
			for (int j : nums2) {
				int temp = i + j;
				map.put(temp, map.getOrDefault(temp, 0) + 1);
			}
		}
		for (int i : nums3) {
			for (int j : nums4) {
				res += map.getOrDefault(-i - j, 0);
			}
		}
		return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}